{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab #2\n",
    "## CS245: Programming Languages\n",
    "## Blank, Fall 2016\n",
    "\n",
    "**Due**: Thursday, Sept 15, 2016\n",
    "\n",
    "In the following problems, please define the function, and test it to make sure it works. I have provided a few examples, but you should test your function thoroughly to make sure that it works. That means, **add more cells for each problem.**\n",
    "\n",
    "If it doesn't work in some instances, you should demonstrate where it fails. Otherwise, I will assume that you don't know that it fails."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Problem: remove-first"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "`remove-first` takes an item and a list, and removes the first occurrence of item in the list. Finish the code in the next cell, and use the following cells to test that it works. Add additional cells to test more variations, or document where it doesn't work correctly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": false,
    "nbgrader": {
     "checksum": "4299cace3e7a29a5a87f268cd0e2f897",
     "grade": true,
     "grade_id": "remove-first",
     "locked": false,
     "points": 10,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-first 'a '())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-first 'a '(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-first 'a '(a a a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-first 'a '(b c a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-first 'a '(a a b c a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-first 'a '(b c d))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Problem: remove-all"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`remove-all` takes an item and a list and removes all occurrences of item from the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": false,
    "nbgrader": {
     "checksum": "a666f205add86b1d7b76c8d669c21064",
     "grade": true,
     "grade_id": "remove-all",
     "locked": false,
     "points": 10,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-all 'a '())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-all 'a '(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-all 'a '(a a a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-all 'a '(b a c a d a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Problem: remove-nth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`remove-nth` takes a number (0-based indexing), an item, and a list. It removes the nth instance of item in the list. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": false,
    "nbgrader": {
     "checksum": "7f4d9f2ecba65bf8673a5820b7947248",
     "grade": true,
     "grade_id": "remove-nth",
     "locked": false,
     "points": 10,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-nth 0 'a '(a b a c a d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-nth 1 'a '(a b a c a d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(remove-nth 2 'a '(a b a c a d))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Problem: substitute"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`substitute` takes an item to search for, an item to replace it, and a list. The function will find all instances of the old item and replace it with the new item."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": false,
    "nbgrader": {
     "checksum": "fd259fc126c9f76cf273df2462bcf592",
     "grade": true,
     "grade_id": "substitute",
     "locked": false,
     "points": 10,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(substitute 'old 'new '())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(substitute 'old 'new '(old))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(substitute 'old 'new '(old old a b c old))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Problem: substitute*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`substitute*` works just like `substitute` but will find all instances no matter how deeply hidden they are inside sublists of the given list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": false,
    "nbgrader": {
     "checksum": "8504481207120b35ebb2108f9766d6ff",
     "grade": true,
     "grade_id": "substitute-all",
     "locked": false,
     "points": 10,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(substitute* 'old 'new '((old)((((old apple bannan)) (a b c old d e))) old test ((word)) (old) old))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6. Problem: infix->prefix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`infix->prefix` will convert expressions given in infix notation to prefix notation. It gives an error if you attempt to operate on an empty list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": false,
    "nbgrader": {
     "checksum": "86268c60d13e761ebbb4b679dcaab926",
     "grade": true,
     "grade_id": "infix-prefix",
     "locked": false,
     "points": 20,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(infix->prefix 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(infix->prefix '(1 + 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(infix->prefix '((1 + 2) * (8 / 9)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(infix->prefix '())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7. Problem: eval-infix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "`eval-infix` will evaluate infix expressions. It should handle +, *, /, and -. It should give an error otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": false,
    "nbgrader": {
     "checksum": "13767bd515a1a5a5c60d9b549c3c5f93",
     "grade": true,
     "grade_id": "eval-infix",
     "locked": false,
     "points": 20,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(eval-infix 42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(eval-infix '(1 + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(eval-infix '(2 * (3 + 7)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(eval-infix '((8 / 9) * (3 + 7)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(eval-infix '(1 ^ 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reflections\n",
    "\n",
    "The reflection cell is the most import cell in this lab... in all labs. In your reflection, you should:\n",
    "\n",
    "* Reflect! Think and comment on what you have learned this lab, and this week. Connect the ideas onto your own life, and experiences.\n",
    "* Feel free to comment on what you found challenging, and what you found intuitive.\n",
    "* How does Scheme differ from Python?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "fd25da50d920439579ae721eee54c9f7",
     "grade": true,
     "grade_id": "reflections",
     "locked": false,
     "points": 50,
     "solution": true
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto Scheme 3",
   "language": "scheme",
   "name": "calysto_scheme"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "scheme"
   },
   "mimetype": "text/x-scheme",
   "name": "scheme",
   "pygments_lexer": "scheme"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}